package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {
	public static void main(String[] args) {
		List<String> set = new ArrayList<String>();
		//set.add("cat");
		//set.add("sand");
		//set.add("dog");
		//set.add("cats");
		//set.add("and");
		
		set.add("aaaa");
		set.add("aaa");
		WordBreak object = new WordBreak();
//		ArrayList<String> list = object.wordBreak2("catsanddogs", set);
		ArrayList<String> list = object.wordBreak2("aaaaaaa", set);
		System.out.println(list);
	}

	// Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, 
	//determine if s can be segmented into a space-separated sequence of one or more dictionary words. 
	//You may assume the dictionary does not contain duplicate words
	
	//最初始的想法
	//TLE
	public boolean wordBreak1_1(String s, List<String> wordDict) {
		if (s == null || s.length() <= 0) {
			return true;
		}
		// 比如aaaaa....a,字典为[a, aa, aaa, ...]这样就会超时
		int length = s.length();
		for (int i = 0; i < length; i++) {
			String substring = s.substring(0, i + 1);
			if (wordDict.contains(substring)) {
				if (i == length - 1) {
					return true;
				}
				if (wordBreak(s.substring(i + 1, length), wordDict)) {
					return true;
				}
			}
		}
		return false;
	}

	
	public boolean wordBreak(String s, List<String> wordDict) {
        if(s == null || s.length() <= 0){
             return true;
        }
        int length = s.length();
        //记录s[0...i - 1]是否能够由字典中构成
        boolean[] f = new boolean[length + 1];
        
        f[0] = true;
        
        //因为f[i + 1]才是表示的str[0...i]是否可以组成
        //f[i + 1] = f[i + 1 - str.lenth] && str.equals(s.substring(i + 1 - str.length + 1, i + 1));
        //str 为字典中所有的字符串
        for(int i = 1; i <= length; i++){
            for(String str: wordDict){
                int curLength = str.length();
                if(curLength <= i){
                    if(f[i - curLength]){
                        if(s.substring(i - curLength, i).equals(str)){
                            f[i] = true;
                            break;
                        }
                    }
                }                
            }
        }
        return f[length];
    }
	
	//应对字符串很小，而字典很大
	public boolean wordBreakAnother(String s, Set<String> dict) {
		if (s == null || s.length() == 0)
			return false;

		int n = s.length();

		// dp[i] represents whether s[0...i] can be formed by dict
		boolean[] dp = new boolean[n];

		//为了应对字符串的长度很小，而字典包含有数百万个单词的极端情况
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				String sub = s.substring(j, i + 1);

				if (dict.contains(sub) && (j == 0 || dp[j - 1])) {
					dp[i] = true;
					break;
				}
			}
		}

		return dp[n - 1];
	}
	
	public boolean wordBreak(String s, Set<String> dict) {
		if (s == null || s.length() <= 0 || dict == null) {
			return false;
		}
		int wordLength = 0;
		int sLength = s.length();
		//result[i] 表示到前i个字符中能否在字典中找到相应的
		boolean[] result = new boolean[sLength + 1];
		result[0] = true;
		for (int i = 1; i <= sLength; i++) {
			for (String string : dict) {
				wordLength = string.length();
				if (wordLength <= i) {
					if(result[i - wordLength]){
						if(s.substring(i - wordLength, i).equals(string)){
							result[i] = true;
						}
					}
				}
			}
		}
		return result[sLength];
	}
	
	
	//word breakII, 
	//For example, given
//	s = "catsanddog",
//	dict = ["cat", "cats", "and", "sand", "dog"].
//
//	A solution is ["cats and dog", "cat sand dog"]
	
	private List<String> wordDict;
	public  ArrayList<String> wordBreak2(String s, List<String> dict) {
		ArrayList<String> list = new ArrayList<String>();
//		StringBuilder builder = new StringBuilder();
		List<String> builder = new ArrayList<String>();
		if (s == null || s.length() <= 0 || dict == null) {
			return list;
		}
		this.wordDict = dict;
		int sLength = s.length();
		int wordLength = 0;
		boolean[] result = new boolean[sLength + 1];
		result[0] = true;
		
		for (int i = 1; i <= sLength; i++) {
			for (String string : dict) {
				wordLength = string.length();
				if (wordLength <= i && (result[i - wordLength]
						&& s.substring(i - wordLength, i).equals(string))) {
					result[i] = true;
				}
			}
		}
		//如果不能组成，直接返回
		if(!result[sLength]){
		    return list;
		}
		realWordBreak2(s, 0, builder, list, result);
		return list;
    }

	//由于可以使用重复的单词，所以最好的解决办法就是使用递归，一旦匹配，就使用DFS来查找是否有合适的
	//否则返回函数继续查找下一个
	//Time Limit Exceeded  超时了
	public static void realWordBreak2(String s, Set<String> dict, int start,
			String combineString, ArrayList<String> list) {
		if (start == s.length()) {
			list.add(combineString);
		}
		for (int i = start; i < s.length(); i++) {
			String sub = s.substring(start, i + 1);
			if (dict.contains(sub))
				// 注意初始combineString的值为“”，也就是length为0
				realWordBreak2(s, dict, i + 1,
						combineString + (combineString.length() == 0 ? "" : " ") + sub, list);
		}
	}
	
	//判断是否可能，减少搜索次数
	//感觉这个StringBuilder没写好
	//还是超时了
	//原来是对不能组成的也在进行相应的操作
	public void realWordBreak2(String s, int start,
			StringBuilder combine, ArrayList<String> list, boolean[] possible) {
		//如果start的位置并不能匹配，直接返回
		if(!possible[start]){
			return;
		}
		if (start == s.length()) {
			combine.deleteCharAt(combine.length() - 1);
			list.add(new String(combine));
			//combine.delete(0, combine.length());
			return;
		}
		int length = s.length();
		for (int i = start; i < length; i++) {
			String sub = s.substring(start, i + 1);
			if (wordDict.contains(sub)){
				realWordBreak2(s, i + 1,
						new StringBuilder(combine).append(sub).append(" "), list, possible);
				//此时combine还需要remove啊
				//combine.delete(combine.length() - sub.length(), combine.length() + 1);
			}
		}
	}
	
	//https://discuss.leetcode.com/topic/53065/java-solution-dp-dfs-beats-91-10
	public void realWordBreak2(String s, int start, List<String> list, List<String> result,
			boolean[] possible){
        if (start == s.length()) {
            StringBuilder sb = new StringBuilder();
            for (String str : list) {
                sb.append(str);
                sb.append(" ");
            }
            sb.deleteCharAt(sb.length() - 1);
            result.add(sb.toString());
            return;
        }
        if (!possible[start]) {
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (!wordDict.contains(s.substring(start, i + 1))) {
                continue;
            }
            list.add(s.substring(start, i + 1));
            realWordBreak2(s, i + 1, list, result, possible);
            list.remove(list.size() - 1);
        }
    }
}
